446. Arithmetic Slices II - Subsequence

Description

Solution

DP to check out the previous subsequence number satisfied requirement.

dp[i][d] = In position i, the number satisfied requirement that difference is d

Code

typedef long long LL;
class Solution {
    // int res = 0;
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        vector<unordered_map<LL,int>> dp(nums.size()+1);
        int res = 0;
        for(int i = 1; i < nums.size(); i++){
            for(int j = 0; j < i; j++){
                LL d = 1LL * nums[i] - nums[j];
                int cnt = ((dp[j].find(d) != dp[j].end()) ? dp[j][d] : 0);
                res += cnt;
                dp[i][d] += cnt+1;
            }
        }
        return res;
    }
};